package project3.association;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import project3.datasets.Attribute;
import project3.datasets.DataSet;
import project3.datasets.DiscreteAttribute;
import project3.datasets.Instance;
import project3.util.Trace;


/**
 * @author 
 * 
 * Apriori algorithm for extraction for association rules 
 * 
 */
public final class Apriori {

	private final double minimumSupportPercent;

	private final double minimumConfidencePercent;
	
	private final DataSet dataSet;

	private final int minSupport;
	
	/**
	 * @param minimumSupportPercent
	 * @param minimumConfidencePercent
	 * @param dataSet
	 */
	public Apriori(double minimumSupportPercent,
			double minimumConfidencePercent, DataSet dataSet) {
		super();
		this.minimumSupportPercent = minimumSupportPercent;
		this.minimumConfidencePercent = minimumConfidencePercent;
		this.dataSet = dataSet;

		this.minSupport = calculateMinimunSupportForDataSet();
	}

	/**
	 * @return
	 */
	int calculateMinimunSupportForDataSet() {
		return (int) (minimumSupportPercent * (double) dataSet.size() + 0.5);
	}

	
	/**
	 * @param rule
	 * @return
	 */
	double calculateConfidenceForRule(AssociationRule rule) {
		int ruleCount = count(rule);

		int consequenceCount = count(rule.getConsequence());

		return (double) ruleCount / (double) consequenceCount;
	}

	/**
	 * @param rule
	 * @return
	 */
	int count(AssociationRule rule) {
		int count = 0;
		out: for (Instance instance : dataSet) {
			ItemSet premise = rule.getPremise();
			double[] premiseRawValues = premise.getRawValues();

			for (int i = 0; i < premiseRawValues.length; i++) {
				if (premise.getValueAt(i) == -1) {
					continue;
				}
				if (instance.getValueAt(i) != premise.getValueAt(i)) {
					continue out;
				}
			}

			ItemSet consequence = rule.getConsequence();
			double[] consequenceRawValues = consequence.getRawValues();

			for (int i = 0; i < consequenceRawValues.length; i++) {
				if (consequence.getValueAt(i) == -1) {
					continue;
				}
				if (instance.getValueAt(i) != consequence.getValueAt(i)) {
					continue out;
				}
			}

			count++;
		}
		return count;
	}
	
	/**
	 * @return
	 */
	List<ItemSet> buildSingletons() {
		List<ItemSet> singletons = prepareSingletons();
		for (ItemSet itemSet : singletons) {
			int support = calculateSupportForItemSet(itemSet);

			if (support >= minSupport) {
				itemSet.setSupport(support);
			}
		}
		return singletons;
	}

	/**
	 * @param itemSet
	 * @return
	 */
	int calculateSupportForItemSet(ItemSet itemSet) {
		double[] intemSetRawValues = itemSet.getRawValues();

		int support = 0;
		out: for (Instance instance : dataSet) {
			for (int i = 0; i < intemSetRawValues.length; i++) {
				if (intemSetRawValues[i] == -1) {
					continue;
				}
				if (instance.getValueAt(i) != intemSetRawValues[i]) {
					continue out;
				}
			}
			support++;
		}
		return support;
	}

	/**
	 * @return
	 */
	List<ItemSet> prepareSingletons() {
		List<ItemSet> singletons = new LinkedList<ItemSet>();
		Attribute[] attributes = dataSet.getAttributes();
		for (int i = 0; i < attributes.length; i++) {
			DiscreteAttribute attribute = ((DiscreteAttribute) attributes[i]);
			String[] values = attribute.getCategories();
			for (int j = 0; j < values.length; j++) {
				ItemSet itemSet = new ItemSet(attributes.length);
				itemSet.setValue(i, attribute.encode(values[j]));
				singletons.add(itemSet);
			}
		}
		return singletons;
	}

	
	/**
	 * @return
	 */
	public Map<Integer, List<ItemSet>> extractLargeItemsets(){
		
		List<ItemSet> singletons = this.buildSingletons();
		if (singletons.isEmpty()) {
			Trace.warning("No item set with min support = "
					+ this.minimumSupportPercent + " was found");

			return null;
		}

		Map<Integer, List<ItemSet>> itemSets = findLargeItems(singletons);

		return itemSets;
	}
	
	/**
	 * @param itemSet
	 * @return
	 */
	int count(ItemSet itemSet) {
		double[] itemSetValues = itemSet.getRawValues();

		int count = 0;
		out: for (Instance instance : this.dataSet) {
			for (int i = 0; i < itemSetValues.length; i++) {
				if (itemSetValues[i] == -1) {
					continue;
				}

				if (instance.getValueAt(i) != itemSetValues[i]) {
					continue out;
				}
			}

			count++;
		}

		return count;
	}

	/**
	 * @param itemSets
	 * @return
	 */
	public  AssociationRule[] extractAssociationRules(
			Map<Integer, List<ItemSet>> itemSets) {
		
		List<AssociationRule> rules = new LinkedList<AssociationRule>();
		for (Map.Entry<Integer, List<ItemSet>> entry : itemSets.entrySet()) {
			for (ItemSet itemSet : entry.getValue()) {
				List<AssociationRule> rulesWithOneItemInTheConsequence = generateAllRulesWithOneItemInTheConsequence(itemSet);

				List<AssociationRule> allOtherRules = generateAllOtherRules(rulesWithOneItemInTheConsequence);

				rules.addAll(rulesWithOneItemInTheConsequence);
				rules.addAll(allOtherRules);
			}
		}
		
		for(Iterator<AssociationRule> ruleIterator = rules.iterator();ruleIterator.hasNext();) {
			AssociationRule rule = ruleIterator.next();
			
			if (rule.getConfidence() < this.minimumConfidencePercent) {
				//Trace.warning("Removing rule: " + rule);
				
				ruleIterator.remove();
			}
		}
		
		return rules.toArray(new AssociationRule[rules.size()]);
		//return rules;
	}

	/**
	 * Generates rules with more than one element in the consequence side.
	 * 
	 * @param rulesWithOneItemInTheConsequence
	 * @return
	 */
	List<AssociationRule> generateAllOtherRules(
			List<AssociationRule> rulesWithOneItemInTheConsequence) {
		List<AssociationRule> allRules = new LinkedList<AssociationRule>();
		for (AssociationRule ruleWithOneConsequence : rulesWithOneItemInTheConsequence) {

			List<AssociationRule> rulesToExpand = new LinkedList<AssociationRule>();

			rulesToExpand.add(ruleWithOneConsequence);

			while (rulesToExpand.size() > 0) {
				AssociationRule rule = rulesToExpand.remove(0);

				ItemSet premise = rule.getPremise();
				if (premise.size() == 1) {
					continue;
				}

				double[] premiseRawValues = premise.getRawValues();
				double[] consequenceRawValues = rule.getConsequence()
						.getRawValues();

				for (int i = 0; i < premiseRawValues.length; i++) {
					if (premiseRawValues[i] == -1) {
						continue;
					}

					double[] newPremiseRawValues = premiseRawValues.clone();

					double[] newConsequenceRawValues = consequenceRawValues
							.clone();

					newConsequenceRawValues[i] = newPremiseRawValues[i];
					newPremiseRawValues[i] = -1;

					ItemSet newPremise = new ItemSet(newPremiseRawValues);
					newPremise.setSupport(this.calculateSupportForItemSet(newPremise));
					
					ItemSet newConsequence = new ItemSet(newConsequenceRawValues); 
					newConsequence.setSupport(this.calculateSupportForItemSet(newConsequence));
					
					AssociationRule newRule = new AssociationRule(
							newPremise, newConsequence);

					calculateSupport(newRule);
					
					double confidence = this
							.calculateConfidenceForRule(newRule);

					newRule.setConfidence(confidence);

					allRules.add(newRule);

					if (newRule.getPremise().size() > 1) {
						rulesToExpand.add(newRule);	
					}
				}
			}
		}
		return allRules;
	}

	/**
	 * @param newRule
	 */
	private void calculateSupport(AssociationRule newRule) {
		int count = this.count(newRule);
		
		double support = (double) count / (double) this.dataSet.size();
		
		newRule.setSupport(support);
	}

	/**
	 * @param itemSet
	 * @return
	 */
	List<AssociationRule> generateAllRulesWithOneItemInTheConsequence(
			ItemSet itemSet) {
		List<AssociationRule> rules = new LinkedList<AssociationRule>();

		double[] rawValues = itemSet.getRawValues();
		for (int i = 0; i < rawValues.length; i++) {
			if (rawValues[i] != -1) {
				ItemSet consequence = new ItemSet(rawValues.length);
				consequence.setValue(i, rawValues[i]);

				ItemSet premise = new ItemSet(rawValues.length);

				for (int j = 0; j < rawValues.length; j++) {
					if (j == i) {
						continue;
					}
					if (rawValues[j] != -1) {
						premise.setValue(j, rawValues[j]);
					}
				}

				premise.setSupport(this.calculateSupportForItemSet(premise));
				
				consequence.setSupport(this.calculateSupportForItemSet(consequence));
				
				AssociationRule rule = new AssociationRule();
				rule.setPremise(premise);
				rule.setConsequence(consequence);

				calculateSupport(rule);
				
				double confidence = this.calculateConfidenceForRule(rule);

				rule.setConfidence(confidence);

				//Trace.info("Adding rule: " + rule);

				rules.add(rule);
			}
		}

		return rules;
	}

	/**
	 * @param singletons
	 * @return
	 */
	Map<Integer, List<ItemSet>> findLargeItems(List<ItemSet> singletons) {
		Map<Integer, List<ItemSet>> allSets = new HashMap<Integer, List<ItemSet>>();

		List<ItemSet> newItemSets = singletons;

		boolean continueExtractingItems = true;
		int k = 2;

		while (continueExtractingItems) {
			newItemSets = buildItems(newItemSets, singletons);

			if (newItemSets.isEmpty()) {
				continueExtractingItems = false;
				continue;
			}

			allSets.put(k, new LinkedList<ItemSet>(newItemSets));
			k++;
		}

		return allSets;
	}

	/**
	 * @param itemSets
	 * @param singletons
	 * @return
	 */
	private List<ItemSet> buildItems(List<ItemSet> itemSets,
			List<ItemSet> singletons) {
		Set<ItemSet> newItemSets = new HashSet<ItemSet>();
		for (int i = 0; i < itemSets.size(); i++) {
			double[] first = itemSets.get(i).getRawValues();

			for (int j = 0; j < singletons.size(); j++) {
				double[] singletonRawValues = singletons.get(j).getRawValues();

				for (int k = 0; k < first.length; k++) {
					if (first[k] == -1 && singletonRawValues[k] != -1) {
						double[] merged = first.clone();
						merged[k] = singletonRawValues[k];

						ItemSet mergedSet = new ItemSet(merged);

						int support = this
								.calculateSupportForItemSet(mergedSet);

						mergedSet.setSupport(support);

						if (support >= this.minSupport) {

							newItemSets.add(mergedSet);
						}
					}
				}
			}

		}
		return new LinkedList<ItemSet>(newItemSets);
	}

	public RuleToString getDefaultRuleToString() {

		return new RuleToString(this.dataSet);
	}

	public double getMinimumSupport() {
		return this.minimumSupportPercent;
	}

	public double getMinimumConfidence() {
		return this.minimumConfidencePercent;
	}

	public DataSet getDataSet() {
		return this.dataSet;
	}

}
